//
// Created by liushuai on 2021/2/8.
//

#include "exist.h"

<<<<<<< HEAD:cxx/algorithm/src/exist.cc
bool dfsBoard(vector<vector<char>> &board, vector<vector<bool>> &visied, int r, int c, string word) {
    if (word.empty())
        return true;

    int rows = board.size();
    int cols = board[0].size();
    if (r < 0 || r >= rows || c < 0 || c >= cols) //越界说明无法找到，返回false
        return false;

    if (!visied[r][c] && board[r][c] == word[0]) {
        visied[r][c] = true;
        // 左右上下查找找到则word为空，返回true
        bool flag = dfsBoard(board, visied, r, c + 1, word.substr(1, word.size() - 1)) ||
                    dfsBoard(board, visied, r, c - 1, word.substr(1, word.size() - 1)) ||
                    dfsBoard(board, visied, r + 1, c, word.substr(1, word.size() - 1)) ||
                    dfsBoard(board, visied, r - 1, c, word.substr(1, word.size() - 1));
        if(flag)
            return true;
        else
            visied[r][c]= false;//没有找到则以r，c开始的访问不合法，将之前的修改改回
    }
    return false;//不满足dfs条件，直接返回false
}

bool exist(vector<vector<char>> &board, string& word) {
    int rows = board.size();
    int columns = board[0].size();
    vector<bool> rowBool(columns, false);
    vector<vector<bool>> visited(rows, rowBool);
    static int start = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < columns; c++) {

            if (board[r][c]==word[0]&&dfsBoard(board, visited, r, c, word))
                return true;
        }
    }
    return false;
=======
bool dfsBoard(vector<vector<char>> &board, vector<vector<bool>> &visied, int r,
              int c, string word) {
  if (word.empty()) return true;

  int rows = board.size();
  int cols = board[0].size();
  if (r < 0 || r >= rows || c < 0 || c >= cols)  // 越界说明无法找到，返回false
    return false;

  if (!visied[r][c] && board[r][c] == word[0]) {
    visied[r][c] = true;
    // 左右上下查找找到则word为空，返回true
    bool flag =
        dfsBoard(board, visied, r, c + 1, word.substr(1, word.size() - 1)) ||
        dfsBoard(board, visied, r, c - 1, word.substr(1, word.size() - 1)) ||
        dfsBoard(board, visied, r + 1, c, word.substr(1, word.size() - 1)) ||
        dfsBoard(board, visied, r - 1, c, word.substr(1, word.size() - 1));
    if (flag)
      return true;
    else
      visied[r][c] =
          false;  // 没有找到则以r，c开始的访问不合法，将之前的修改改回
  }
  return false;  // 不满足dfs条件，直接返回false
}

bool exist(vector<vector<char>> &board, string &word) {
  int rows = board.size();
  int columns = board[0].size();
  vector<bool> rowBool(columns, false);
  vector<vector<bool>> visited(rows, rowBool);
  static int start = 0;
  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < columns; c++) {
      if (board[r][c] == word[0] && dfsBoard(board, visited, r, c, word))
        return true;
    }
  }
  return false;
>>>>>>> dev:cxx/algorithm/common/src/exist.cc
}